import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Num2363 {
    //给你两个二维整数数组items1 和items2，表示两个物品集合。每个数组items有以下特质：
    //items[i] = [valuei, weighti] 其中valuei表示第i件物品的价值，weighti表示第 i件物品的 重量。
    //items中每件物品的价值都是 唯一的。
    //请你返回一个二维数组ret，其中ret[i] = [valuei, weighti]，weighti是所有价值为valuei物品的重量之和。
    //注意：ret应该按价值 升序排序后返回。
    public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
        Arrays.sort(items1, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        Arrays.sort(items2, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int len1 = items1.length;
        int len2 = items2.length;
        int index1 = 0,index2 = 0;
        List<List<Integer>> ret = new ArrayList<>();
        while (index1 != len1 && index2 != len2) {
            //按照升序依次合并
            if (items1[index1][0] == items2[index2][0]) {
                List<Integer> res = new ArrayList<>();
                res.add(items1[index1][0]);
                res.add(items1[index1][1] + items2[index2][1]);
                ret.add(res);
                index1++;
                index2++;
            }else {
                if (items1[index1][0] < items2[index2][0]) {
                    List<Integer> res = new ArrayList<>();
                    res.add(items1[index1][0]);
                    res.add(items1[index1][1]);
                    ret.add(res);
                    index1++;
                }else {
                    List<Integer> res = new ArrayList<>();
                    res.add(items2[index2][0]);
                    res.add(items2[index2][1]);
                    ret.add(res);
                    index2++;
                }
            }
        }
        //第一个数组合并完成，第二个还没走完
        if (index1 == len1 && index2 != len2) {
            while (index2 != len2) {
                List<Integer> res = new ArrayList<>();
                res.add(items2[index2][0]);
                res.add(items2[index2][1]);
                ret.add(res);
                index2++;
            }
        }
        //第二个数组合并完成，第一个还没走完
        if (index2 == len2 && index1 != len1) {
            while (index1 != len1) {
                List<Integer> res = new ArrayList<>();
                res.add(items1[index1][0]);
                res.add(items1[index1][1]);
                ret.add(res);
                index1++;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[][] item1 = new int[][]{{1,1},{3,2},{2,3}};
        int[][] item2 = new int[][]{{2,1},{3,2},{1,3}};
        Num2363 num2363 = new Num2363();
        System.out.println(num2363.mergeSimilarItems(item1,item2));
    }
}
